package com.yunsom.testdemo.leetcode;

import java.util.*;
import java.util.Map.Entry;

public class AlgorithmPractice {

    /*
    算法概览：
    二分搜索 Binary Search
    分治 Divide Conquer
    宽度优先搜索 Breadth First Search
    深度优先搜索 Depth First Search
    回溯法 Backtracking
    双指针 Two Pointers
    动态规划 Dynamic Programming
    扫描线 Scan-line algorithm
    快排 Quick Sort数据结构部分栈 Stack
     */
    public static void main(String[] args) {

        System.out.println("查找数组中特定值");
        int[] nums1 = new int[]{0,2,4,5,6,8,10,20,99};
        System.out.println(getArraySpecificValue(nums1, 0));
        System.out.println(getArraySpecificValue(nums1, 2));
        System.out.println(getArraySpecificValue(nums1, 99));

        System.out.println("生成非递减的数组值的平方的数组");
        int[] nums2 = new int[]{-5,-3,-2,-1};
        System.out.println(Arrays.toString(sortedSquares(nums2)));

        System.out.println("轮转数组");
        int[] nums3 = new int[]{-5,-2, 0, 4,5,6,8,10,20,99};
        rotate(nums3, 3);
        System.out.println(Arrays.toString(nums3));

        System.out.println("移动零");
        int[] nums4 = new int[]{0,0,0,1,0,0,0,3,0,4,12,0,0};
        moveZeroes(nums4);
        System.out.println(Arrays.toString(nums4));

    }

    //给定一个 n 个元素有序的（升序）整型数组 nums和一个目标值 target，写一个函数搜索 nums 中的 target，
    //如果目标值存在返回下标，否则返回 -1。
    //示例 1:
    //输入: nums = [-1,0,3,5,9,12], target = 9
    //输出: 4
    //解释: 9 出现在 nums 中并且下标为 4
    //示例 2:
    //输入: nums = [-1,0,3,5,9,12], target = 2
    //输出: -1
    //解释: 2 不存在 nums 中因此返回 -1
    //提示：
    //    你可以假设 nums 中的所有元素是不重复的。
    //    n 将在 [1, 10000]之间。
    //    nums 的每个元素都将在 [-9999, 9999]之间。
    public static int getArraySpecificValue(int[] nums, int target){
        // 二分法
        int start = 0;
        int end = nums.length-1;
        while(end >= start){
            int mid = (start + end)/2;
            int value = nums[mid];
            if (value == target){
                return mid;
            } else if (value < target){
                start = mid +1;
            } else{
                end = mid -1;
            }
        }
        return -1;
    }

    //第一个错误的版本
    //你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。
    //由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
    //假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
    //你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。
    //实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
    //示例 1：
    //输入：n = 5, bad = 4
    //输出：4
    //解释：
    //调用 isBadVersion(3) -> false
    //调用 isBadVersion(5) -> true
    //调用 isBadVersion(4) -> true
    //所以，4 是第一个错误的版本。
    //示例 2：
    //输入：n = 1, bad = 1
    //输出：1
    public static int firstBadVersion(int n) {
        // 二分法
        int start = 0;
        int end = n;
        while(end > start){
            int mid = start + (end - start)/2;
            if (isBadVersion(mid) ){
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }
    public static boolean isBadVersion(int version){
        int badVersion = new Random().nextInt(10);
        System.out.println("badVersion:" + badVersion);
        return badVersion == version;
    }

    //搜索插入位置
    //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    //请必须使用时间复杂度为 O(log n) 的算法。
    //示例 1:
    //输入: nums = [1,3,5,6], target = 5
    //输出: 2
    //示例 2:
    //输入: nums = [1,3,5,6], target = 2
    //输出: 1
    //示例 3:
    //输入: nums = [1,3,5,6], target = 7
    //输出: 4
    //提示:
    //    1 <= nums.length <= 104
    //    -104 <= nums[i] <= 104
    //    nums 为 无重复元素 的 升序 排列数组
    //    -104 <= target <= 104
    public static int searchInsert(int[] nums, int target) {
        // 二分法
        int start = 0;
        int end = nums.length - 1;
        int res = nums.length;
        while(end >= start){
            int mid = start + (end -start)/2;
            if (nums[mid] < target){
                start = mid + 1;
            } else if (nums[mid] >= target){
                res = mid;
                end = mid - 1;
            }
        }
        return res;
    }

    // 有序数组的平方
    //  给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
    //  示例 1：
    //  输入：nums = [-4,-1,0,3,10]
    //  输出：[0,1,9,16,100]
    //  解释：平方后，数组变为 [16,1,0,9,100]
    //  排序后，数组变为 [0,1,9,16,100]
    //  示例 2：
    //  输入：nums = [-7,-3,2,3,11]
    //  输出：[4,9,9,49,121]
    //  提示：
    //  1 <= nums.length <= 104
    //  -104 <= nums[i] <= 104
    //  nums 已按 非递减顺序 排序
    //  进阶：
    //  请你设计时间复杂度为 O(n) 的算法解决本问题
    //  思路与算法
    //  显然，如果数组nums 中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；
    //  如果数组nums 中的所有数都是负数，那么将每个数平方后，数组会保持降序。
    //  这样一来，如果我们能够找到数组nums 中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。
    //  具体地，我们设neg为数组nums中负数与非负数的分界线，也就是说，nums[0]到nums[neg] 均为负数，
    //  而nums[neg+1]到nums[n−1] 均为非负数。当我们将数组nums 中的数平方后，那么nums[0]到nums[neg]单调递减，
    //  nums[neg+1]到nums[n−1] 单调递增。由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。
    //  具体地，使用两个指针分别指向位置neg 和neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。
    //  当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。
    public static int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        for(int i=0,j=n-1,pos=n-1;i<=j;){
            if(nums[i]*nums[i] > nums[j]*nums[j]){
                result[pos] = nums[i]*nums[i];
                i++;
            } else {
                result[pos] = nums[j]*nums[j];
                j--;
            }
            pos--;
        }

        return result;
    }

    //轮转数组
    //给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
    //示例 1:
    //输入: nums = [1,2,3,4,5,6,7], k = 3
    //输出: [5,6,7,1,2,3,4]
    //解释:
    //向右轮转 1 步: [7,1,2,3,4,5,6]
    //向右轮转 2 步: [6,7,1,2,3,4,5]
    //向右轮转 3 步: [5,6,7,1,2,3,4]
    //示例 2:
    //输入：nums = [-1,-100,3,99], k = 2
    //输出：[3,99,-1,-100]
    //解释:
    //向右轮转 1 步: [99,-1,-100,3]
    //向右轮转 2 步: [3,99,-1,-100]
    //提示：
    //1 <= nums.length <= 105
    //-231 <= nums[i] <= 231 - 1
    //0 <= k <= 105
    //进阶：
    //尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
    //你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);
    }
    public static void reverse(int[] num, int j, int k){
        while(j < k){
            int temp = num[j];
            num[j] = num[k];
            num[k] = temp;
            j++;
            k--;
        }
    }

    //移动零
    //给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
    //请注意 ，必须在不复制数组的情况下原地对数组进行操作。
    //示例 1:
    //输入: nums = [0,1,0,3,12]
    //输出: [1,3,12,0,0]
    //示例 2:
    //输入: nums = [0]
    //输出: [0]
    //提示:
    //1 <= nums.length <= 104
    //-231 <= nums[i] <= 231 - 1
    //进阶：你能尽量减少完成的操作次数吗？
    public static void moveZeroes(int[] nums) {
        if (nums.length ==1){
            return;
        }
        // [0,0,1,3,12]
        // [1,0,0,3,12]
        // [1,3,0,0,12]
        // [1,3,12,0,0]
        int left = 0;
        int right = 1;
        for (int i = 0; i < nums.length; i++) {
            if (right<=nums.length-1){
                if (nums[left]==0){
                    if (nums[right]!=0){
                        swap(nums, left, right);
                        left++;
                    }
                    right++;
                }
            }
        }
    }
    private static void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    //两数之和 II - 输入有序数组
    //给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。
    //如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
    //以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
    //你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
    //你所设计的解决方案必须只使用常量级的额外空间。空间复杂度要求：O(1)
    //示例 1：
    //输入：numbers = [2,7,11,15], target = 9
    //输出：[1,2]
    //解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
    //示例 2：
    //输入：numbers = [2,3,4], target = 6
    //输出：[1,3]
    //解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
    //示例 3：
    //输入：numbers = [-1,0], target = -1
    //输出：[1,2]
    //解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
    //提示：
    //2 <= numbers.length <= 3 * 104
    //-1000 <= numbers[i] <= 1000
    //numbers 按 非递减顺序 排列
    //-1000 <= target <= 1000
    //仅存在一个有效答案
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length-1;
        int sum;
        while (right>left){
            sum = numbers[left] + numbers[right];
            if (sum==target){
                return new int[]{left+1,right+1};
            } else if (sum<target){
                left++;
            } else{
                right--;
            }
        }
        return new int[]{-1,-1};
    }

    // 反转字符串
    //编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
    //不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
    //示例 1：
    //输入：s = ["h","e","l","l","o"]
    //输出：["o","l","l","e","h"]
    //示例 2：
    //输入：s = ["H","a","n","n","a","h"]
    //输出：["h","a","n","n","a","H"]
    //提示：
    //1 <= s.length <= 105
    //s[i] 都是 ASCII 码表中的可打印字符
    public static void reverseString(char[] s) {
        char temp;
        int left = 0;
        int right = s.length-1;
        while(left<right){
            temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }

    //反转字符串中的单词 III
    //给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
    //示例 1：
    //输入：s = "Let's take LeetCode contest"
    //输出："s'teL ekat edoCteeL tsetnoc"
    //示例 2:
    //输入： s = "God Ding"
    //输出："doG gniD"
    //提示：
    //1 <= s.length <= 5 * 104
    //s 包含可打印的 ASCII 字符。
    //s 不包含任何开头或结尾空格。
    //s 里 至少 有一个词。
    //s 中的所有单词都用一个空格隔开。
    public static String reverseWords(String s) {
        StringBuffer ret = new StringBuffer();
        int length = s.length();
        int i = 0;
        while (i < length) {
            int start = i;
            while (i < length && s.charAt(i) != ' ') {
                i++;
            }
            for (int p = start; p < i; p++) {
                ret.append(s.charAt(start + i - 1 - p));
            }
            while (i < length && s.charAt(i) == ' ') {
                i++;
                ret.append(' ');
            }
        }
        return ret.toString();
    }
}
